import sys

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        maxPath = [-sys.maxsize]
        
        def traverse(root):
            if not root: return -sys.maxsize
            left = traverse(root.left)
            right = traverse(root.right)
            # path from left to right
            path = max(left, root.val, right, left+root.val, root.val+right, left+root.val+right)
            maxPath[0] = max(maxPath[0], path)
            # path form parent to this node
            path = root.val+max(0, left, right)
            maxPath[0] = max(maxPath[0], path)
            return path
        
        traverse(root)
        return maxPath[0]